package A_review;

public class HeapSort7_14 {

    public int[] heapSort(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        int length = nums.length;

        heapAll(nums);

        //TODO:2023/7/14 这一块的遍历需要倒着来  注意这里是i>=1
//        for (int i = length-1; i>=1 ; i--) {
        //TODO:2023/7/14 i--  不用写 啥都不用做  哈哈
        for (int i = length - 1; i >= 1; ) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            i--;
            adjustHeap(nums, 0, i);
        }
        return nums;
    }

    public void heapAll(int[] nums) {
        int length = nums.length;
        for (int i = (length - 1) / 2; i >= 0; i--) {
            adjustHeap(nums, i, length - 1);
        }
    }

    public void adjustHeap(int[] nums, int k, int end) {
        int j;
        //TODO:2023/7/14 满足2*k+1 <=1  也就是根节点的左子树在堆调整的范围内 也就是根节点存在左孩子
        while (2 * k + 1 <= end) {
            j = 2 * k + 1;
            //TODO:2023/7/14   比较左右子树的大小数值
            //TODO:2023/7/14 需要带 =号
            if (j + 1 <= end && nums[j + 1] > nums[j]) {
                j++;
            }
            //TODO:2023/7/14 左右子节点中数值较大的与根节点进行交换
            if (nums[j] > nums[k]) {
                int temp = nums[j];
                nums[j] = nums[k];
                nums[k] = temp;
            } else {
                //TODO:2023/7/14 如果左右子节点的值都不大于 根节点就不行行堆的调整 直接跳出循环
                break;
            }
            k = j;
        }
    }


    public static void main(String[] args) {
        HeapSort7_14 heapSort7_14 = new HeapSort7_14();
        int[] cur = {2, 3, 54, 6, 1};
        int[] ints = heapSort7_14.heapSort(cur);
        for (int a :
                ints) {
            System.out.println(a);


        }

    }


}
